Computer interconnection and communication systems are typically referred to as networks. Networks are generally classified according to their geographical extent as local area networks (LANs), metropolitan area networks (MANs) and wide area networks (WANs).
LANs are commonly used to transmit messages between relatively closely located computers. LANs are characterized by several basic types of organizational architectures including linear, ring and mesh. For example, Ethernet is a widely used linear LAN and FDDI (fiber distributed data interface) is a widely used ring LAN. Unlike linear and ring LANs, mesh LANs have an arbitrary topology. A LAN connects addressable devices, such as printers, servers, and workstations. The addressable devices are called stations. In some LANs, such as Ethernet, each station has a globally unique and unchanging address, called its unique identifier (UID).
Stations on a LAN communicate by sending and receiving data packets or groups of data packets. In general, a packet contains the station address UID of the packet source, the station address UID of the packet destination and a payload. Packets can be distinguished by their destination address type. For example, a unicast packet is a packet with a station address as its destination. A multicast packet is a packet having a group address UID as its destination. Stations on a LAN can also communicate by sending a multicast packet to a group of destinations. Typically one bit in the UID is dedicated to distinguish station addresses from group addresses. Typically also one particular group address is dedicated to signify the group of all stations. A multicast packet with a group address of all the stations as its destination is called a broadcast packet.
LANs have basic limitations such as the number of stations, bandwidth and physical extent. A LAN offers, however, a useful high-speed communication service that facilitates data sharing and client-server interactions among its stations. In order to extend the benefits of a LAN beyond the basic limitations of a single LAN, forwarding devices, known as bridges, are used to interconnect LANs to form extended LANs.
An extended LAN is a collection of LANs interconnected by bridges. Bridges are addressable devices that forward packets back and forth between the bridged LANs. An extended LAN architecture with bridged LANs is referred to as a bridged network architecture. Each of the individual component LANs is known as a network segment. The network segment is also simply referred to as the segment.
Since bridges are addressable devices, they are stations on each of their connected LANs. Stations that are not bridges are known as end stations. For simplicity, end stations are also called hosts. A bridge includes a plurality of bridge ports, each one corresponding to a connection between the bridge and a segment. Bridge functions that pertain to a specific connection between the bridge and a segment are typically described as being performed by the corresponding port. In general, a single bridge may connect to any number of LANs, although typically a bridge connects to a small number of LANs, say between two and eight. Notwithstanding hosts, an extended LAN consists of segments, bridges and the connections between segments and bridges.
Structurally, an extended LAN can be represented as a graph. A graph is a mathematical object consisting of a set of nodes and a set of edges. Each edge in a graph connects two nodes. In a graph representing the extended LAN, the nodes represent the segments and bridges and the edges represent the connections, in the extended LAN, between the segments and bridges. This graph is called the network topology graph. The network topology graph is also referred to simply as the topology.
Transparent bridging requires that the bridges dynamically maintain address information for each of their connected LANs in order to facilitate the routing of packets. Bridges learn about the presence of hosts by listening to packets passing by. From this listening, bridges obtain the addresses of hosts on their connected LANs. Bridges use host addresses to help make forwarding decisions. Whenever the topology of a network changes, for instance with a LAN or bridge is added to or removed from the network, or a host is moved from one LAN to another, the host location information stored by the bridges may become invalid. On the other hand, much of the lost location information stored by the bridges may remain valid.
As previously mentioned, bridges solve the learning process by listening to packets passing by. The learning problem is solved because any host packets that a bridge hears arriving on an active connection must be from hosts that can be reached only by transmitting back on this active connection. By listening to packets the bridge learns which of its active connections to use to reach a given host. In other words, the bridge learns the direction (in the spanning tree) to a given host. The learning process, while well developed, nevertheless uses considerable system resources. Further, as the scale of an extended LAN increases, the total amount of communication between hosts on different segments tends to increase, and the total amount of learning by each bridge also increases. Having to restart the learning process from a state of total ignorance every time there is any change in the network topology negatively impacts network performance, in part because the rate of network topology changes tends to increase as number of hosts, LANs and bridges in an extended LAN increases. Therefore, there is a need to effectively and efficiently manage the host location information in response to bridged network topology changes. The present invention addresses this and related problems.